1) Field of the Invention
The present invention relates to an associative memory apparatus and a routing apparatus suitable for use in address switching at a relay point in a network, for example.
2) Description of the Related Art
With rapid spread of use of the Internet technology, speed-up of the network becomes more important issue. Particularly, a router that is a relay point in the network is required to distribute a packet (for example, IP [Internet Protocol] datagram) flowing in the network on a proper route in a high-speed routing operation.
In such the routing operation on the network, a CAM (Content Addressable/Associative Memory) device is heretofore used as an apparatus for searching a destination address. The CAM device performs a process to search a destination address for an inputted packet by hardware.
When used as the above destination address searching apparatus, the CAM device is required to have a function of performing a, so-called, Longest Prefix Match searching to select the longest prefix bits which are not masked among addresses matching in the search.
As the CAM device performing the above longest prefix match searching, there is a Ternary-CAM 100 as shown in FIG. 15, for example. The ternary CAM 100 searches for a matching address (a coinciding address in the address bit matching) among entered destination addresses 104 on the basis of an address 101 that is a search key.
The ternary CAM 100 shown in FIG. 15 comprises a plurality of entry units 103-1 to 103-n, each of which can store a destination address (address 1 to n) and prefix bits 105 corresponding to the destination address 104, match lines 102 provided for the respective entry units 103-1 to 103-n, and a priority encoder 106.
The destination addresses 104 stored in the respective entry units 103-1 to 103-n are beforehand arranged in order of length of consecutive bits (a length of consecutive bits of value xe2x80x9c1xe2x80x9d) in the prefix bits 105.
In the case of value xe2x80x9c1xe2x80x9d in the prefix bits 105, a condition that a result of matching is not ignored is given in the matching of corresponding address bit digit. In the case of value xe2x80x9c0xe2x80x9d, a condition that a result of the matching is ignored (Don""t care condition) is given in the matching of corresponding address bit digit.
In this case, a destination address having the longest prefix bits 105 is stored in the entry unit 103-1, and a destination address having the second longest prefix bits is stored in the entry unit 103-2. In the entry units 103-3 to 103-n, destination addresses are stored in order of length of the prefix bits.
When search match signals (match) from the entry units 103-1 to 103-n compete, the priority encoder 106 outputs a search match signal having a longer prefix bits 105 from the entry unit 103-1, 103-2, . . . or 103-n as a result of the searching.
FIG. 16 is a block diagram showing a CAM cell configuring each of the entry units 103-1 to 103-n shown in FIG. 15. Namely, each of the entry units 103-1 to 103-n comprises the CAM cells 200 shown in FIG. 16 in number corresponding to bits assumed to configure a destination address.
One CAM cell 200 comprises a data register 201 for storing address data of one bit configuring a destination address, a mask register 202 for storing a prefix bit of one bit corresponding to the address data, a comparator 203 for comparing address data from the data register 201 with address data that is a search key from bit lines 206 and 207, and a mask circuit 204 for performing a masking process (refer to a reference character 208) on the basis of a value of the mask register 202.
With the above structure, in the ternary CAM 100 show in FIG. 15, a search for coincidence with an address that is a search key is made in each of the ternary units 103-1 to 103-n. An entry unit 103-1, 103-2, . . . , or 103-n storing a destination address matching with the address that is a search key outputs this effect as a search match signal (match signal) to the priority encoder 106 through the match line 102.
In this case, all entries (destination addresses stored in the entry units 103-1 to 103-n) are arranged in order of length of the prefix bits 105 and accommodated. Therefore, when a plurality of destination addresses match, the priority encoder 106 outputs a match signal from the entry unit 103-1, 103-2, . . . , or 103-n given the highest priority among matching destination addresses in the search as a result of the longest prefix match.
In order to appropriately obtain a result of the longest prefix match in the ternary CAM 100 in FIG. 15, it is necessary to beforehand arrange all entries in order of length of the prefix and accommodate them. Namely, when a new distribution destination is registered or when a distribution destination that becomes not to be used is deleted, it is necessary to add or delete the entry.
When an entry is added, an entry unit 103-1, 103-2, . . . or 103-n to which the entry should be inserted is determined according to the length of the prefix among the entry units 103-1 to 103-n, entries lower than the relevant position are moved down, an entry unit 103-1, 103-2, . . . or 103-n at a position at which the new entry should be added is emptied, after that, the entry to be added is stored. Whereby, the entry can be added without breaking the order of length of the prefix.
When an entry is added or deleted as above, it is necessary to rearrange all the entries in order of prefix, and again accommodate them. However, a series of this updating work requires a considerable time. Moreover, it is necessary to stop the CAM device in service.
Since a high-speed, continuous operation of the CAM device is required to more speed up the network, such the updating work causes serious interruption. With spread of the Internet, there is a demand for a larger-capacity of the CAM because of an increase of the number of entries, or an increase of the number of address bits under application of IPv6 (Internet Protocol version 6). When such the updating work is done on a CAM having a large capacity, a load of the work more increases.
U.S. Pat. No. 6,144,574 discloses an apparatus which accommodates an entry of an arbitrary length at an arbitrary position, obtains a result of full match (multi-match) searching and the longest prefix length in the first search cycle, feeds back the longest prefix length obtained in the first cycle in the second cycle, again carries out the searching operation on the prefix of all the entries, and outputs a matching entry as a result of the longest prefix match searching, while reducing a load of the updating work.
However, the above apparatus requires two search cycles as the searching process. For this, there is a problem that the speed-up is disturbed even in such the configuration where two search cycles are required. In order to satisfy a demand for speed-up and larger-capacity of the above CAM device, it is necessary to provide a technique for more shortening a processing time required to carry out the above searching process twice.
In the light of the above problems, an object of the present invention is to provide an associative memory apparatus and a routing apparatus, which can reduce a load of the updating work, readily cope with an increase of the capacity, and shorten a time for the searching process by outputting longest prefix match in one searching operation.
The present invention therefore provides an associative memory apparatus comprising a plurality of entry units storing bit data to be searched and entry data differing from one another having mask identifying data for masking a necessary bit length required by the bit data, and matching each of the entry data with the bit data that is a search key, a matching-masking state outputting means inputted information reflecting a result of the matching in units of the same bit digit in each of the entry units and a mask identifying bit at the bit digit to output reflected result information mutually reflected among the entry units at each bit digit, each of the entry units comprising a logical operating means for outputting information about a bit length not masked of the entry data by a logical operation using the reflected result information from the matching-masking state outputting means when the entry data stored in its own entry unit matches with the bit data that is the key as a result of the matching, and a search result outputting means for outputting search match information about the search key on the basis of an output signal from the logical operating means only when the entry data stored in its own entry unit is entry data having the longest bit length not masked among all entry data coinciding with the bit data that is the key in the matching.
In the above associative memory apparatus, the entry unit may comprise associative memory cells in number equal to at least bits of the entry data to divide the entry data into data each of one bit and storing the data, and matching the entry data with the bit data that is the search key in units of divided one bit, and a matching result outputting means for reflecting results of matching from the associative memory cells to output information about whether a whole of the entry data coincides with the bit data that is the key as a result of the matching.
Preferably, the associative memory cell comprises a data register for dividing the data to be searched into data each of one bit and storing the divided data, a mask register for storing a mask identifying bit corresponding to the data of one bit stored in the data register, and a matching circuit for matching the bit data that is the key with the entry data in units of divided one bit using bits stored in the data register and the mask register, and the logical operating means comprises a logical operation circuit for performing a logical operation in units of the divided one bit. The logical operation circuit comprises a first logical operation element, only when information that a mask identifying bit from the mask register represents that data of one bit stored in a corresponding data register is not masked and information about coincidence between the entry data and the bit data as a result of the matching from the matching result outputting means are inputted, outputting this effect as a first operation result to the matching-mask state outputting means, and a second operation element, only when a logical operation result from the first logical operation element is the first operation result and an output result from the matching-masking state outputting means at the adjacent bit digit is other than the first operation result, outputting this effect as a second operation result to the search result outputting means. And, the search result outputting means outputs the search match information when inputted the second operation result from the second logical operation element.
In the above associative memory apparatus, the matching-masking state outputting means may be configured with a line stretched in common among the associative memory cells storing bits at the same digit of the entry data.
The associative memory apparatus according to this invention may comprise an external connecting means for connecting a plurality of entry blocks to one another, each of which entry blocks comprises a plurality of the entry units, wherein the matching-masking state outputting means outputs the result information mutually reflected among the entry units configuring each of the entry block through the external connecting means.
In the above associative memory apparatus, preferably, the external connecting means connects in series or in parallel the matching-masking state outputting means in each of the entry blocks. In such case, a control circuit for disconnecting at least one entry block among a plurality of the entry blocks connected to one another may be interposed in the external connecting means.
Each of the entry blocks may comprise an encoding means for encoding output signals from the matching-masking state outputting means, and the external connecting means may comprise a bus line being able to bus-communicate the output signals encoded by the encoding means among the entry blocks.
The matching-masking state outputting means may be configured with a line stretched in common among the associative memory cells storing bits at the same digit each of which is a part of each entry data.
In such case, the matching-masking state outputting means may be configured with a line stretched in common among the associative memory cells storing bits at the same digit in higher bits excluding at least lower one bit of each entry data.
Further, at least lower one bit of each of the entry data may be a weight bit giving a weight in matching of bit data to be searched.
Alternatively, the matching-masking state outputting means may be configured with a line stretched in common among the associative memory cells storing bits at the same digit in lower bits excluding at least higher one bit of each entry data. Further, at least one bit of each of the entry data may be weight bit giving a weight in matching of bit data to be searched.
Preferably, the search result outputting means is configured with a wired-connection line wired-connecting output signals from the second logical operation elements. The matching-masking state outputting means is configured with a wired-connection line wired-connecting output signals from the first logical operation elements. The first logical operation element or the second logical operation element may be configured with a CMOS logical circuit, an NMOS logical circuit, or a PMOS logical circuit.
The present invention further provides a routing apparatus comprising an associative memory storing a destination address correspondingly to an output destination route, and an output route determining unit analyzing a destination address attached to an inputted packet, and performing a routing process such that the packet is transferred to an output destination route obtained by referring to the associative memory, the routing apparatus comprising the associative memory cell comprising a plurality of entry units for storing bit data configuring a destination address to be searched and entry data differing from one another having mask identifying data for masking a necessary bit length in the bit data, and matching the entry data with the bit data configuring the destination address that is a search key, a matching-masking state outputting means inputted information reflecting a result of the matching in units of the same bit digit in each of the entry units and a mask identifying bit at the bit digit to output reflected result information mutually reflected among the entry units at each bit digit, each of the entry units comprising a logical operating means for outputting information about a bit length not masked of the entry data by a logical operation using the reflected result information from the matching-masking state outputting means when the entry data stored in its own entry unit matches with the bit data that is a key as a result of the matching, and a search result outputting means for outputting search match information about the search key on the basis of an output signal from the logical operating means only when the entry data stored in its own entry unit is entry data having the longest bit length not masked among all entry data coincides with the bit data that is a key in the matching.
According to this invention, the entry unit has the logical operation means and the search result outputting means. It is thereby possible to reduce a load of the updating work to shorten the time, and readily cope with an increase of the capacity. It is also possible to output a longest prefix match result in one searching operation without a clock, shorten the searching time, simplify the updating work, and shorten the time. This contributes to speed-up of the network.
According to this invention, a plurality of entry blocks may be mutually connected by the external connecting means, which provides similar advantages to those provided by the first embodiment. It is also possible to increase the entry data that the apparatus can accommodate as a whole, and readily cope with an increase of the number of entries in the network.